package com.shuo.map;

import java.util.HashMap;
import java.util.Map;

/**
 * - 模仿LinkedHashMap实现LRU
 * - 尾插法, 最新在tail, eldest在head
 * - 该例子不同于LinkedHashMap是get和put都会将操作节点往最新处挪
 */
public class LRU_Map {
    private int capSize;
    private Map<String, Entry> map;
    private Entry head; // eldest就往head丢
    private Entry tail;

    public LRU_Map(int capSize) {
        this.capSize = capSize;
        map = new HashMap<>();
    }

    public void put(String key, Integer value) {
        Entry entry = new Entry();
        entry.key = key;
        entry.value = value;
        map.put(key, entry);
        afterEntryInsertion(entry);
        if (removeEldestEntry()) {
            map.remove(head.key);
            afterEntryRemoval(head);
        }
    }

    public Integer get(String key) {
        Entry entry = map.get(key);
        if (entry == null) return null;
        afterEntryAccess(entry);
        return entry.value;
    }

    public void remove(String key) {
        Entry entry = map.get(key);
        map.remove(entry.key);
        afterEntryRemoval(entry);
    }

    private boolean removeEldestEntry() {
        return map.size() > capSize;
    }

    private void afterEntryInsertion(Entry entry) {
        if (head == null) {
            head = entry;
            tail = entry;
        } else {
            Entry pre = tail;
            pre.after = entry;
            tail = entry;
            entry.before = pre;
        }

    }

    private void afterEntryAccess(Entry entry) {
        Entry cur = entry;
        Entry pre = entry.before;
        Entry post = entry.after;
        Entry last = tail;
        cur.after = null; // 试一下把这一句注释掉,有神奇的事情发生
        if (pre == null) {
            head = post;
        } else {
            pre.after = post;
        }

        if (post == null) {
            last = pre;
        } else {
            post.before = pre;
        }

        if (last == null) {
            head = cur;
        } else {
            cur.before = last;
            last.after = cur;
        }
        tail = cur;
    }

    private void afterEntryRemoval(Entry entry) {
        Entry cur = entry;
        Entry pre = entry.before;
        Entry post = entry.after;
        cur.before = cur.after = null;
        if (pre == null) {
            head = post;
        } else {
            pre.after = post;
        }

        if (post == null) {
            tail = pre;
        } else {
            post.before = pre;
        }
    }

    @Override
    public String toString() {
        String ret = "";
        Entry entry = head;
        while (entry != null) {
            ret += entry.toString() + " ";
            entry = entry.after;
        }
        return ret;
    }

    static final class Entry {
        private Entry before;
        private Entry after;
        private String key;
        private Integer value;

        @Override
        public String toString() {
            return "Entry{" +
                    "key='" + key + '\'' +
                    ", value=" + value +
                    '}';
        }
    }


    public static void main(String[] args) {
        LRU_Map map = new LRU_Map(3);
        map.put("1", 1);
        map.put("2", 2);
        map.put("3", 3);
        map.put("4", 4);
        map.put("5", 5);
        map.get("3");
        System.out.println(map);
    }
}
